Modem telecommunication systems exchange data in packets. A typical packet has a header and a data payload. An Internet Protocol (IP) packet is an example of such a packet. An individual packet may have a number of different protocols. There are many circumstances in which it is desirable to process packets. In general, packet processing involves retrieving information from a packet and then performing some action on a packet. As a trivial example, packet processing might involve looking up the destination IP address in an IP packet and using the IP address to identify a port via which the packet should be forwarded to reach the destination IP address.
Packet processing systems typically must be fast enough to process packets in real time as they are received at a device. As a result, high-speed packet processors are most typically implemented in hardware. A typical packet processor comprises an application-specific integrated circuit (ASIC) which is hardwired to determine values at specific offsets within received packets and to perform certain actions on the basis of those values. ASICs can handle very large packet rates but are not very flexible. If a protocol is changed, for example, by changing the offset within a packet at which certain information is located, then the ASIC will no longer work properly. Programmable network processors are much more flexible than ASICs but lack in performance.
Programmable network processors are much more flexible than ASICs but lack in performance. Some network processors use a tree-search methodology to determine what action(s) to perform on a packet. In such a network processor, a first bit field, which typically comprises a few bits, is retrieved from the packet and used as an index to access a memory. The memory contains a value which indicates a next bit field to take (and may also specify an action to be applied to the packet). A sequence of one or memory accesses is required to identify a final action to apply to the packet. The final action might, for example, specify whether or not the packet should be dropped, forwarded to a specific port, have a certain quality of service provided to it, and so on.
Some widely-used protocols are characterized by protocol header fields which are sparse. Such protocols are specified, at least in part, by a parameter which has a large valid range but only a few specific values of the parameter are significant. An example of such a protocol is internet protocol version 4 (IP v.4). In this widely-used protocol, packet destinations are specified by 32-bit numbers. Valid IP addresses can have any of nearly 232 different values. In most real world packet processing situations, however, particular actions need to be taken only for a few specific IP addresses or subnets.
Each bit field retrieved from a packet being processed is typically used as an address to access a memory directly. Where the bit field contains a value of a parameter in a sparse protocol header field, (such as an IP address) then a large memory is typically required to accommodate the valid range of possible values that the parameter could have in packets being processed.
Often a device cannot accommodate a large memory internally and so the large memories must be external to the packet processing device. This slows memory access and decreases the number of memory accesses that can be made in the time allowed for processing each packet. This is a problem because it is generally necessary to make several memory accesses to arrive at the final action for a particular packet. The packet may have a protocol stack containing information regarding several protocols.
There is a need for packet processing devices and methods which can provide high throughput and yet are more flexible than hard-wired ASICs.